Abstract: An intersection graph of n vertices assumes that each vertex is equipped with a subset of a global label set. Two vertices share an edge
when their label sets intersect. Random IntersectionGraphs (RIGs) (as defined in [18, 31]) consider label sets formed by the following experiment:
each vertex, independently and uniformly, examines all the labels (m in total) one by one. Each examination is independent and the vertex
succeeds to put the label in her set with probability p. Such graphs nicely capture interactions in networks due to sharing of resources among nodes.
We study here the problem of efficiently coloring (and of finding upper bounds to the chromatic number) of RIGs. We concentrate in a range
of parameters not examined in the literature, namely: (a) m = n{\'a} for less than 1 (in this range, RIGs differ substantially from the Erd¨os- Renyi random graphs) and (b) the selection probability p is quite high
(e.g. at least ln2 n m in our algorithm) and disallows direct greedy colouring methods.
We manage to get the following results:
For the case mp ln n, for any constant < 1 − , we prove that np colours are enough to colour most of the vertices of the graph with high probability (whp). This means that even for quite dense
graphs, using the same number of colours as those needed to properly colour the clique induced by any label suffices to colour almost all of the vertices of the graph. Note also that this range of values of m, p
is quite wider than the one studied in [4].
� We propose and analyze an algorithm CliqueColour for finding a proper colouring of a random instance of Gn,m,p, for any mp >=ln2 n. The algorithm uses information of the label sets assigned to the
vertices of Gn,m,p and runs in O (n2mp2/ln n) time, which is polynomial in n and m. We also show by a reduction to the uniform random
intersectiongraphs model that the number of colours required by the algorithm are of the correct order of magnitude with the actual
chromatic number of Gn,m,p.
⋆ This work was partially supported by the ICT Programme of the European Union under contract number ICT-2008-215270 (FRONTS). Also supported by Research Training Group GK-693 of the Paderborn Institute for Scientific Computation
(PaSCo).
� We finally compare the problem of finding a proper colouring for Gn,m,p to that of colouring hypergraphs so that no edge is monochromatic.We show how one can find in polynomial time a k-colouring of the vertices of Gn,m,p, for any integer k, such that no clique induced by only one label in Gn,m,p is monochromatic. Our techniques are novel and try to exploit as much as possible the hidden structure of random intersectiongraphs in this interesting range.
Abstract: We investigate random intersectiongraphs, a combinatorial model that quite accurately abstracts distributed networks with local interactions between nodes blindly sharing critical resources from a limited globally available domain. We study important combinatorial properties (independence and hamiltonicity) of such graphs. These properties relate crucially to algorithmic design for important problems (like secure communication and frequency assignment) in distributed networks characterized by dense, local interactions and resource limitations, such as sensor networks. In particular, we prove that, interestingly, a small constant number of random, resource selections suffices to make the graph hamiltonian and we provide tight evaluations of the independence number of these graphs.
Abstract: In this work, we overview some results concerning communication combinatorial properties in random intersectiongraphs and uniform random intersectiongraphs. These properties relate crucially to algorithmic design for important problems (like secure communication and frequency assignment) in distributed networks characterized by dense, local interactions and resource limitations, such as sensor networks. In particular, we present and discuss results concerning the existence of large independent sets of vertices whp in random instances of each of these models. As the main contribution of our paper, we introduce a new, general model, which we denote G(V, χ, f). In this model, V is a set of vertices and χ is a set of m vectors in ℝm. Furthermore, f is a probability distribution over the powerset 2χ of subsets of χ. Every vertex selects a random subset of vectors according to the probability f and two vertices are connected according to a general intersection rule depending on their assigned set of vectors. Apparently, this new general model seems to be able to simulate other known random graph models, by carefully describing its intersection rule.
Abstract: We work on an extension of the Population Protocol model of Angluin et al. that allows edges of the communication graph, G, to have states that belong to a constant size set. In this extension, the so called Mediated Population Protocol model (MPP), both uniformity and anonymity are preserved. We here study a simplified version of MPP, the Graph Decision Mediated Population Protocol model (GDM), in order to capture MPP's ability to decide (stably compute) graph languages (sets of communication graphs). To understand properties of the communication graph is an important step in almost any distributed system. We prove that any graph language is undecidable if we allow disconnected communication graphs. As a result, we focus on studying the computational limits of the GDM model in (at least) weakly connected communication graphs only and give several examples of decidable graph languages in this case. To do so, we also prove that the class of decidable graph languages is closed under complement, union and intersection operations. Node and edge parity, bounded out-degree by a constant, existence of a node with more incoming than outgoing neighbors and existence of some directed path of length at least k=O(1) are some examples of properties whose decidability is proven. To prove the decidability of graph languages we provide protocols (GDMs) for them and exploit the closure results. Finally, we prove the existence of symmetry in two specific communication (sub)graphs which we believe is the first step towards the proof of impossibility results in the GDM model. In particular, we prove that there exists no GDM, whose states eventually stabilize, to decide whether G contains some directed cycle of length 2 (2-cycle).
Abstract: We investigate important combinatorial and algorithmic properties of $G_{n, m, p}$ random intersectiongraphs. In particular, we prove that with high probability (a) random intersectiongraphs are expanders, (b) random walks on such graphs are ``rapidly mixing" (in particular they mix in logarithmic time) and (c) the cover time of random walks on such graphs is optimal (i.e. it is $\Theta(n \log{n})$). All results are proved for $p$ very close to the connectivity threshold and for the interesting, non-trivial range where random intersectiongraphs differ from classical $G_{n, p}$ random graphs.
Abstract: We investigate the existence and efficient algorithmic
construction of close to optimal independent sets in random models
of intersectiongraphs. In particular, (a) we propose \emph{a new model} for random intersectiongraphs
($G_{n, m, \vec{p}}$) which includes the model of
\cite{RIG} (the ``uniform" random intersectiongraphs model) as an
important special case. We also define an interesting variation of
the model of random intersectiongraphs, similar in spirit to
random regular graphs. (b) For this model we derive \emph{exact formulae} for the mean
and variance of the number of independent sets of size $k$ (for
any $k$) in the graph. (c) We then propose and analyse \emph{three algorithms} for the
efficient construction of large independent sets in this model.
The first two are variations of the greedy technique while the
third is a totally new algorithm. Our algorithms are analysed for
the special case of uniform random intersectiongraphs.
Our analyses show that these algorithms succeed in finding
\emph{close to optimal} independent sets for an interesting range
of graph parameters.
Abstract: Random IntersectionGraphs is a new class of random graphs introduced in [5], in which each of n vertices randomly and independently chooses some elements from a universal set, of cardinality m. Each element is chosen with probability p. Two vertices are joined by an edge iff their chosen element sets intersect. Given n, m so that m=n{\'a}, for any real {\'a} different than one, we establish here, for the first time, tight lower bounds p0(n,m), on the value of p, as a function of n and m, above which the graph Gn,m,p is almost certainly Hamiltonian, i.e. it contains a Hamilton Cycle almost certainly. Our bounds are tight in the sense that when p is asymptotically smaller than p0(n,m) then Gn,m,p almost surely has a vertex of degree less than 2. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection model. Interestingly, Hamiltonicity appears well below the general thresholds, of [4], at which Gn,m,p looks like a usual random graph. Thus our bounds are much stronger than the trivial bounds implied by those thresholds.
Our results strongly support the existence of a threshold for Hamiltonicity in Gn,m,p.
Abstract: In the uniform random intersectiongraphs model, denoted by Gn;m;, to each vertex v
we assign exactly randomly chosen labels of some label set M of m labels and we connect every
pair of vertices that has at least one label in common. In this model, we estimate the independence
number (Gn;m;), for the wide, interesting range m = n; < 1 and = O(m1=4). We also prove
the hamiltonicity of this model by an interesting combinatorial construction. Finally, we give a brief
note concerning the independence number of Gn;m;p random intersectiongraphs, in which each vertex
chooses labels with probability p.
Abstract: We study the on-line versions of two fundamental graph problems, maximum independent set and minimum coloring, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds; we also present an improved upper bound for on-line coloring.
Abstract: We study the on-line version of the maximum independent set problem, for the case of disk graphs which are graphs resulting
from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower
bounds for deterministic on-line independent set algorithms and present new upper and lower bounds.
Abstract: Random IntersectionGraphs, Gn,m,p, is a class of random graphs introduced in Karoński (1999) [7] where each of the n vertices chooses independently a random subset of a universal set of m elements. Each element of the universal sets is chosen independently by some vertex with probability p. Two vertices are joined by an edge iff their chosen element sets intersect. Given n, m so that m=left ceilingn{\'a}right ceiling, for any real {\'a} different than one, we establish here, for the first time, a sharp threshold for the graph property “Contains a Hamilton cycle”. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection graph model.
Abstract: In this work we consider the problem of finding Hamilton Cycles in graphs derived from the uniform random intersectiongraphs model $G_{n, m, p}$. In particular, (a) for the case $m = n^{\alpha}, \alpha>1$ we give a result that allows us to apply (with the same probability of success) any algorithm that finds a Hamilton cycle with high probability in a $G_{n, k}$ graph (i.e. a graph chosen equiprobably form the space of all graphs with $k$ edges), (b) we give an \textbf{expected polynomial time} algorithm for the case $p = \textrm{constant}$ and $m \leq \alpha \sqrt{\frac{n}{\log{n}}}$ for some constant $\alpha$, and (c) we show that the greedy approach still works well even in the case $m = o(\frac{n}{\log{n}})$ and $p$ just above the connectivity threshold of $G_{n, m, p}$ (found in \cite{Singerphd}) by giving a greedy algorithm that finds a Hamilton cycle in those ranges of $m, p$ with high probability.
Abstract: We work on an extension of the Population Protocol model of Angluin et al. that allows edges of the communication graph, G, to have states that belong to a constant size set. In this extension, the so called Mediated Population Protocol model (MPP), both uniformity and anonymity are preserved. We study here a simplified version of MPP in order to capture MPP's ability to stably compute graph properties. To understand properties of the communication graph is an important step in almost any distributed system. We prove that any graph property is not computable if we allow disconnected communication graphs. As a result, we focus on studying (at least) weakly connected communication graphs only and give several examples of computable properties in this case. To do so, we also prove that the class of computable properties is closed under complement, union and intersection operations. Node and edge parity, bounded out-degree by a constant, existence of a node with more incoming than outgoing neighbors, and existence of some directed path of length at least k=O(1) are some examples of properties whose computability is proven. Finally, we prove the existence of symmetry in two specific communication graphs and, by exploiting this, we prove that there exists no protocol, whose states eventually stabilize, to determine whether G contains some directed cycle of length 2.
Abstract: We investigate the existence and efficient algorithmic construction
of close to optimal independent sets in random models of intersectiongraphs. In particular, (a) we propose a new model for random
intersectiongraphs (Gn,m,p) which includes the model of [10] (the “uniform”
random intersectiongraphs model) as an important special case.
We also define an interesting variation of the model of random intersectiongraphs, similar in spirit to random regular graphs. (b) For this
model we derive exact formulae for the mean and variance of the number
of independent sets of size k (for any k) in the graph. (c) We then propose
and analyse three algorithms for the efficient construction of large
independent sets in this model. The first two are variations of the greedy
technique while the third is a totally new algorithm. Our algorithms are
analysed for the special case of uniform random intersectiongraphs.
Our analyses show that these algorithms succeed in finding close to optimal
independent sets for an interesting range of graph parameters.
Abstract: We investigate the existence and efficient algorithmic construction of close to opti-
mal independent sets in random models of intersectiongraphs. In particular, (a) we
propose a new model for random intersectiongraphs (Gn,m,~p) which includes the
model of [10] (the “uniform” random intersectiongraphs model) as an important
special case. We also define an interesting variation of the model of random intersec-
tion graphs, similar in spirit to random regular graphs. (b) For this model we derive
exact formulae for the mean and variance of the number of independent sets of size
k (for any k) in the graph. (c) We then propose and analyse three algorithms for
the efficient construction of large independent sets in this model. The first two are
variations of the greedy technique while the third is a totally new algorithm. Our
algorithms are analysed for the special case of uniform random intersectiongraphs.
Our analyses show that these algorithms succeed in finding close to optimal in-
dependent sets for an interesting range of graph parameters.
Abstract: In this paper we examine spectral properties of random intersectiongraphs when the number of vertices is equal to the number of labels. We call this class symmetric random intersectiongraphs. We examine symmetric random intersectiongraphs when the probability that a vertex selects a label is close to the connectivity threshold $\tau_c$. In particular, we examine the size of the second eigenvalue of the transition matrix corresponding to the Markov Chain that describes a random walk on an instance of the symmetric random intersection graph $G_{n, n, p}$. We show that with high probability the second eigenvalue is upper bounded by some constant $\zeta < 1$.
Abstract: In this paper we examine spectral properties of random intersectiongraphs when the number
of vertices is equal to the number of labels. We call this class symmetric random intersectiongraphs.
We examine symmetric random intersectiongraphs when the probability that a vertex selects a label
is close to the connectivity threshold ¿c. In particular, we examine the size of the second eigenvalue of
the transition matrix corresponding to the Markov Chain that describes a random walk on an instance
of the symmetric random intersection graph Gn,n,p. We show that with high probability the second
eigenvalue is upper bounded by some constant ³ < 1.